package prime;

import java.util.Random;

import util.Util;

public class RabinMiller {

	public static boolean rabinMiller(int n, int t)
	{
		if(n < 4 || n == 5) return true;
		if(n % 2 == 0 || n % 5 == 0 || n % 3 == 0 || n % 7 == 0)
			return false;
		
		int d = n - 1;
		int s = 0;
		
		while(d % 2 == 0)
		{
			d /= 2;
			s++;
		}
		
		int a, x;
		Random rnd = Util.getRnd();
		
		for(int i = 0; i < t; ++i)
		{
			a = rnd.nextInt(n - 3) + 2;
			x = Util.modPowI(a, d, n);
			if(x == 1 || x == n - 1)
				continue;
			
			int j = 0;
			for(j = 1; j < s; ++j)
			{
				x = Util.modPowI(x, 2, n);
				if(x == 1)
					return false;
				if(x == n - 1)
					break;
			}
			if(j == s)
				return true;
		}
		
		return true;
	}
	
	public static void main(String[] args) {
		for(int i = 5; i < 100; ++i)
			if(rabinMiller(i, 5000))
				System.out.println(i);
		System.out.println("Done!");
	}

}
